//
// Created by LiuYou on 2021/12/2.
//

#include <iostream>
#include <random>
#include <vector>
#include <iterator>


static int randomNumberFromTheRange(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


/* ===========================[ 快速排序 ]=============================== */

class QuickSort {
public:
    static void quickSort(std::vector<int>& arr) {
        if (arr.empty() || arr.size() == 1) {
            return;
        }

        quickSort( arr, 0, arr.size() - 1 );
    }


    static void quickSort(std::vector<int>& arr, int left, int right) {
        if (left < right) {
            int randomIndex = randomNumberFromTheRange( left, right );
            std::swap( arr[randomIndex], arr[right] );

            const std::vector<int>& partitionRegionRangeIndex = partition( arr, left, right );

            quickSort( arr, left, partitionRegionRangeIndex[0] - 1 );
            quickSort( arr, partitionRegionRangeIndex[1] + 1, right );

        } else {
            return;
        }
    }

    static std::vector<int> partition(std::vector<int>& arr, int left, int right) {
        int leftSide = left - 1;
        int rightSide = right;
        int pivot = arr[right];
        int index = left;

        while (index < rightSide) {
            // 貌似 arr[index] < pivot 这个分支时错误的, 对就是错误的。
            // 现在进行了改进了。那么现在的问题, 为什么注释的内容运行也是正确的?
            if (arr[index] < pivot) {
//                ++index;
//                ++leftSide;
                std::swap( arr[index++], arr[++leftSide] );
            } else if (arr[index] == pivot) {
                ++index;
            } else {
                std::swap( arr[index], arr[--rightSide] );
            }
        }

        std::swap( arr[index], arr[right] );
        return std::vector<int>{leftSide + 1, rightSide};
    }
};


/* ===========================[ 快速排序 ]=============================== */


int main(int argc, char** argv) {
    std::vector<int> arr;
    arr.reserve( 10 );
    for (int i = 0; i < 10; ++i) {
        arr.push_back( randomNumberFromTheRange( 0, 100 ));
    }

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;

    QuickSort::quickSort( arr );

    std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
    std::cout << std::endl;


    return 0;
}
